Bem-vindo à Aula 3 de Conceitos de Inteligência Artificial (PolyU COMP5511). Nesta sessão, fazemos a transição da busca de caminho de agente único para Busca Adversarial, onde os agentes operam em ambientes multiagente competitivos. Também introduzimos Problemas de Satisfação de Restrições (CSPs), um paradigma onde o objetivo é encontrar um estado que satisfaça um conjunto específico de restrições, em vez de um caminho.
Conceitos Centrais
- Busca Adversarial: Foca em algoritmos como Minimax e Poda Alpha-Beta para tomar decisões racionais contra um oponente inteligente.
- Busca em Árvore Monte Carlo (MCTS): Explora a tomada de decisão probabilística, servindo como a base para IAs de jogos modernas como AlphaGo.
- Satisfação de Restrições: Modela problemas usando Variáveis, Domínios e Restrições, resolvidos via Backtracking e Busca Local.
Análise de Complexidade
Em cenários adversariais, a complexidade do espaço de busca é frequentemente definida pelo fator de ramificação do jogo
Aviso de Mudança de Paradigma
Ao contrário da busca padrão (por exemplo, A* ou BFS), onde o ambiente é estático, Busca Adversarial assume que o ambiente (o oponente) tenta ativamente minimizar seu sucesso. Em CSPs, a ordem das ações importa menos do que a validade da atribuição final.
Pseudocódigo Conceitual: Tipos de Agente
1
# Agente Adversarial (Teoria dos Jogos)
2
functionDecide_Move( state):
3
returnMaximize_Utility( Predict_Opponent_Minimization( state))
4
5
# Solucionador de CSP (Lógica de Restrições)
6
functionSolve_CSP( variables, constraints):
7
ifAll_Constraints_Satisfied( assignment):
8
returnassignment
9
else :
10
returnBacktrack_Search( variables )
Roteiro do Curso
Transição da Busca (Aula 2) para Tomada de Decisão Estratégica (Aula 3).